package com.kk.datastructure.search;

import java.util.Arrays;


/**
 * title: 斐波那契查找
 * @author 阿K
 * 2020年12月24日 下午11:34:16 
 */
public class FibSearch {
	public static void main(String[] args) {
		int[] arr = { 1, 8, 10, 89, 1000, 1234 };
		System.out.println(fibSearch(arr, 11));
	}

	/**
	 * 为了得到 mid = low + F(k-1)-1,固需要得到一个斐波那契数列
	 * 
	 * @param a
	 * @return
	 */
	private static int[] fib(int maxSize) {
		int[] f = new int[maxSize];
		f[0] = 1;
		f[1] = 1;
		for (int i = 2; i < f.length; i++) {
			f[i] = f[i - 1] + f[i - 2];
		}
		return f;
	}

	/**
	 * 斐波那契查找算法
	 * 
	 * @param arr 查找原始数组
	 * @param key 查找的关键码
	 * @return -1 表无找到
	 */
	public static int fibSearch(int[] arr, int key) {
		int low = 0;
		int high = arr.length - 1;
		int k = 0;// 表斐波那契分割值的下标
		int mid = 0;// 存放mid值
		int[] f = fib(arr.length);// 获取斐波那契数列

		// 获取斐波那契分割值的下标
		while (high > f[k] - 1) {
			k++;
		}

		// 因 f[k] 的长度 可能大于 arr 的长度，因此 需要构造一个辅助数组 int[] temp
		// 不足的部门使用 0 补充【暂】
		int[] temp = Arrays.copyOf(arr, f[k]);
		// 补零 应为 arr数组的最后一个值 填充到 temp
		// eg：{1,8, 10, 89, 1000, 1234, 0, 0} => {1,8, 10, 89, 1000, 1234, 1234, 1234}
		for (int i = high + 1; i < temp.length; i++) {
			temp[i] = arr[high];
		}

		// 使用 while ,查找 key
		while (low <= high) {
			// 公式：开始不必多问，会慢慢理解
			mid = low + f[k - 1] - 1;
			if (key < temp[mid]) {// 应继续向数组的左边查找(前面
				high = mid - 1;
				// 说明： 为何 k--
				// 1、故 全部元素 = 左边数组 + 右边数组
				// 2、f[k] = f[k-1] + f[k-2]
				// 3、因 前面有 f[k-1] 个元素，所以可以拆分为 f[k-1] = f[k-2] + f[k-3]
				// 4、既在 f[k-1] 的前面继续查找 ， k--
				// 5、既 下次的循环就是 f[k-1-1] -1
				k--;
			} else if (key > temp[mid]) {// 应继续向数组的右边查找(后面
				low = mid + 1;
				// 说明： k-=2;
				// 1、故 全部元素 = 左边数组 + 右边数组
				// 2、f[k] = f[k-1] + f[k-2]
				// 3、因 后面有 f[k-2] 个元素，所以可以拆分为 f[k-1] = f[k-3]+f[k-4]
				// 4、既在f[k-2] 的前面继续查找，k-=2
				// 5、既 下次的循环就是 f[k-1-2] -1
				k -= 2;
			} else {// 找到
					// 需要确定返回的下标
				if (mid <= high) {
					return mid;
				} else {
					return high;
				}
			}
		}
		return -1;
	}
}
